// https: // leetcode.cn/problems/count-complete-tree-nodes/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* dfs(TreeNode* root, int k) {
        if (nullptr == root) return nullptr;
        if (k == 1) return root;

        TreeNode* p = dfs(root, k / 2);
        if (nullptr == p) return nullptr;
        if (k == k / 2 * 2 + 1) return p->right;
        else return p->left;
    }
    int countNodes(TreeNode* root) {
        if (root == nullptr) return 0;
        int l = 0, r = 5e4 + 1;
        while (l + 1 < r) {
            int mid = l + r >> 1;
            if (dfs(root, mid) != nullptr) l = mid;
            else r = mid; 
        }
        return l;
    }
};